package com.stupidzhe.ds.linkedlist;

import java.util.Iterator;

/**
 * @Author: StupidZhe
 * @Date: Created in 2018/3/27
 * @Description: 双向链表 (doubly linked list)
 */
public class DoublyLinkedList<T> implements Iterable<T> {

    public DoublyLinkedList() {
        first = new Element<>(null, null, null);
        last = new Element<>(null, null, null);
        first.next = last;
        last.prev = first;
    }

    // 头结点和尾节点为空节点
    private Element<T> first;
    private Element<T> last;

    private Element<T> currentElement;
    private Integer size = 0;

    @Override
    public Iterator<T> iterator() {
        currentElement = first;
        return new Iterator<T>() {
            @Override
            public boolean hasNext() {
                return currentElement.next != null && currentElement.next != last;
            }

            @Override
            public T next() {
                return (currentElement = currentElement.next).val;
            }
        };
    }

    private class Element<Any> {
        Element<Any> next;
        Element<Any> prev;
        Any val;

        public Element(Element<Any> next, Element<Any> prev, Any val) {
            this.next = next;
            this.prev = prev;
            this.val = val;
        }

    }

    // 突然发现add更形象

    /**
     * add a val to last element
     * The time of adding is a final value
     *
     * @param val the value which will added into the list
     * @return val
     */
    public synchronized T add(T val) {
        Element<T> element = new Element<T>(null, null, val);
        element.next = last;
        Element<T> prevElement = last.prev;
        element.prev = prevElement;
        last.prev = element;
        prevElement.next = element;
        size++;
        return val;
    }

    public synchronized int size() {
        return size;
    }

    public T getFirst() {
        if (size != 0) {
            return first.next.val;
        }
        return null;
    }

    public T getLast() {
        if (size != 0) {
            return last.prev.val;
        }
        return null;
    }

    public synchronized T delete(T val) {
        Element<T> element = first.next;
        while (element.next != null) {
            if (element.val.equals(val)) {
                Element<T> prevElement = element.prev;
                prevElement.next = element.next;
                element.next = prevElement;
                size--;
                return val;
            }
            element = element.next;
        }
        return null;
    }

    public synchronized T delete(T val, int index) {

        return null;
    }

    @Override
    public synchronized String toString() {
        StringBuilder res = new StringBuilder();
        if (size == 0) {
            return "";
        }
        Element<T> element = first.next;
        while (element.next != null) {
            res.append(element.val).append(" ");
            element = element.next;
        }
        return res.toString();
    }

}
